/**
 * Created by zhourh on 2018/7/13.
 *
 * 我们把符合下列属性的数组 A 称作山脉：

 A.length >= 3
 存在 0 < i < A.length - 1 使得A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
 给定一个确定为山脉的数组，返回任何满足 A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] 的 i 的值。



 示例 1：

 输入：[0,1,0]
 输出：1
 示例 2：

 输入：[0,2,1,0]
 输出：1

 二分法
 */
public class PeakIndexInAMountainArray {

    public static void main(String[] args){
        System.out.println(new PeakIndexInAMountainArray().peakIndexInMountainArray2(new int[]{0,1,0}));
        System.out.println(new PeakIndexInAMountainArray().peakIndexInMountainArray2(new int[]{0,2,1,0}));
        System.out.println(new PeakIndexInAMountainArray().peakIndexInMountainArray2(new int[]{0,1,2,3,4}));
    }

    public int peakIndexInMountainArray(int[] A) {
        if (A == null || A.length <= 1) {
            return 0;
        }


        for (int i = 1; i < A.length; i++) {
            if (A[i - 1] >= A[i]) {
                return i - 1;
            }
        }

        return A.length - 1;

    }

    public int peakIndexInMountainArray2(int[] A) {
        if (A == null || A.length <= 1) {
            return 0;
        }

        int min = 0, max = A.length - 1;
        while (max - min > 1 ) {
            int mid = (max + min) / 2;
            if (A[mid] < A[mid + 1]) {
                min = mid + 1;
            } else {
                max = mid;
            }
        }

        return (A[min] > A[max]) ? min : max;
    }

}
